using System;
using System.Collections.Generic;

namespace Graph
{
	public class BinaryHeap<T> : IPQ<T> where T : Knoten, IKey
	{
		public List<T> Heap;

        public void init(int C){}

		public BinaryHeap ()
		{
			Heap = new List<T> ();
		}

		public bool insert (T item)
		{
			Heap.Add (item);
			item.setHeapPos (Heap.Count);
			int aktPos = Heap.Count;
			//TODO heapyfy aufrufen auf item
			if (Heap.Count > 1)
				while (aktPos != 1 && ((IKey)Heap[aktPos - 1]).getKey () < ((IKey)Heap[aktPos / 2 - 1]).getKey ()) {
					T tmp = Heap[aktPos / 2 - 1];
					Heap[aktPos / 2 - 1] = Heap[aktPos - 1];
					Heap[aktPos / 2 - 1].setHeapPos (aktPos / 2);
					Heap[aktPos - 1] = tmp;
					Heap[aktPos - 1].setHeapPos (aktPos);
					aktPos = aktPos / 2;
				}
			
			return true;
		}

		public bool delete (int item)
		{
			if (Heap.Count > 2) {
				T tmp = Heap[item - 1];
				Heap[item - 1] = Heap[Heap.Count - 1];
				Heap[item - 1].setHeapPos (item);
				Heap[Heap.Count - 1] = tmp;
				Heap[Heap.Count - 1].setHeapPos (Heap.Count);
				Heap.RemoveAt (Heap.Count - 1);
				
				// TODO Heapyfy auf item
				heapify (1);
				
				return true;
			}
			
			if (Heap.Count == 1) {
				Heap.RemoveAt (0);
				return true;
			}
			
			if (Heap.Count == 0)
				return false;
			
			return false;
		}

		public T extractHead ()
		{
			if (Heap.Count == 0)
				return default(T);
			
			T Min;
			if (Heap.Count > 1) {
				Min = Heap[0];
				T tmp = Heap[Heap.Count - 1];
				Heap[Heap.Count - 1] = Heap[0];
				Heap[Heap.Count - 1].setHeapPos (Heap.Count);
				Heap[0] = tmp;
				Heap[0].setHeapPos (1);
				Heap.RemoveAt (Heap.Count - 1);
				
				// TODO Heapyfy auf Wurzel
				heapify (1);
			} else {
				Min = Heap[0];
				Heap.RemoveAt (0);
			}
			return Min;	
		}

		public int getMinId ()
		{
			if (Heap.Count == 0)
				return Int16.MinValue;
			return Heap[0].Id;
		}
		
		public double getMinValue ()
		{
			if (Heap.Count == 0)
				return Double.NaN;
			return Heap[0].getKey ();
		}
		
		public int getHeapPositionByNodeIndex (int index)
		{
			int i;
			for (i = 0; i < Heap.Count; i++)
			{
				if (Heap[i].Id == index)
					return Heap[i].getHeapPos ();
			}
			return int.MinValue;
		}
		
		public double getKey (int item)
		{
			return ((IKey)Heap[item - 1]).getKey ();
		}
		
		public bool decreaseKey (int item, double Key)
		{
			((IKey)Heap[item - 1]).setKey (Key);
			
			int aktPos = item;
			if (Heap.Count > 1)
				while (aktPos != 1 && ((IKey)Heap[aktPos - 1]).getKey () < ((IKey)Heap[aktPos / 2 - 1]).getKey ()) {
					T tmp = Heap[aktPos / 2 - 1];
					Heap[aktPos / 2 - 1] = Heap[aktPos - 1];
					Heap[aktPos / 2 - 1].setHeapPos (aktPos / 2);
					Heap[aktPos - 1] = tmp;
					Heap[aktPos - 1].setHeapPos (aktPos);
					aktPos = aktPos / 2;
				}
			
			return true;
		}

		// Vater = abgerundet(2/n)
		// linker Bruder = 2n
		// rechter Bruder = 2n + 1
		private void heapify (int item)
		{
			
			int left = item * 2;
			int right = item * 2;
			int largest = item;
			
			if (left < Heap.Count && ((IKey)Heap[left - 1]).getKey () < ((IKey)Heap[item - 1]).getKey ())
				largest = left;
			
			if (right < Heap.Count && ((IKey)Heap[right - 1]).getKey () < ((IKey)Heap[largest - 1]).getKey ())
				largest = right;
			
			if (largest != item) {
				T tmp = Heap[item - 1];
				Heap[item - 1] = Heap[largest - 1];
				Heap[item - 1].setHeapPos (item);
				Heap[largest - 1] = tmp;
				Heap[largest - 1].setHeapPos (largest);
				heapify (largest);
			}
		}

		public bool isEmpty ()
		{
			return Heap.Count == 0;
		}
	}
}

